A finite state automaton (FSA) is used in various fields such as natural language processing and pattern recognition. For example, the applications of an FSA include searching for specific character strings in a text or searching for patterns of character strings in a text. Meanwhile, a finite state automaton is sometimes also called a finite automaton (FA) or a finite state machine (FSM). In the following explanation, symbols assigned to the transitions in an FSA are called input symbols. Generally, an input symbol is simply called a symbol. Moreover, an input symbol is sometimes also called an alphabet or a character.
An FSA in which the weights are taken into account is called a weighted finite state acceptor. An FSA in which the weights as well as the output symbols are taken into account is called a weighted finite state transducer (WFST). In the following explanation, a weighted finite state acceptor and a weighted finite state transducer (WFST) are collectively called a weighted finite state automaton (WFSA). Moreover, a model obtained by adding more functions to a weighted finite state acceptor or a weighted finite state transducer (WFST) is also assumed to be included in the WFSA as a derived model. Such a WFSA is used in expressing a dictionary or a model required in speech recognition, handwritten-character recognition, or optical character recognition (OCR), or is used in statistical machine translation.
A WFSA that is obtained by transformation from a dictionary of a model may not have the structure suitable for use in pattern recognition. For that reason, there are times when a deformation operation is performed. For example, a technology is known in which, after a deformation operation is performed on a WFSA, the weights are quantized with the aim of reducing the size of the memory area required in storing the WFSA.
However, in the conventional technology, since quantization of the weights is performed after the deformation operation, there are times when unnecessary paths generated during quantization of the weights cannot be eliminated.